﻿// Write a program that reads a rectangular matrix of size N x M and finds in it the square 3 x 3 that has maximal sum of its elements.

using System;

class FindsSquare3x3WithMaxSum
{
    static void Main()
    {
        // read Matix from console
        Console.WriteLine("Enter Matrix Size:");
        int rows;
        do
        {
            Console.Write("Enter Row (N): ");
        } while (!int.TryParse(Console.ReadLine(), out rows) || rows < 3);

        int columns;
        do
        {
            Console.Write("Enter Col (M): ");
        } while (!int.TryParse(Console.ReadLine(), out columns) || columns < 3);

        int[,] matrix = new int[rows, columns];
        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < columns; col++)
            {
                int element;
                do
                {
                    Console.Write("Enter matrix[{0}, {1}] = ", row, col);
                } while (!int.TryParse(Console.ReadLine(), out element));
                matrix[row, col] = element;
            }
        }
        
        int bestSum = int.MinValue;
        int bestRow = 0;
        int bestCol = 0;
        int squareSize = 3;
        for (int row = 0; row < matrix.GetLength(0) - squareSize + 1; row++)
        {
            for (int col = 0; col < matrix.GetLength(1) - squareSize + 1; col++)
            {
                // sum elements of square
                int sum = 0;
                for (int squareRow = row; squareRow < row + squareSize; squareRow++)
                {
                    for (int squareCol = col; squareCol < col + squareSize; squareCol++)
                    {
                        sum += matrix[squareRow, squareCol];
                    }
                }
                if (sum > bestSum)
                {
                    bestSum = sum;
                    bestRow = row;
                    bestCol = col;
                }
            }
        }

        // print square matrix
        Console.WriteLine("Square with maximal Sum({0}) is:", bestSum);
        Console.WriteLine("{");
        for (int row = bestRow; row < bestRow + squareSize; row++)
        {
            for (int col = bestCol; col < bestCol + squareSize; col++)
            {
                Console.Write(matrix[row, col]);
                if (row != bestRow + squareSize - 1 || col != bestCol + squareSize - 1)
                {
                    Console.Write(", ");
                }
            }
            Console.WriteLine();
        }
        Console.WriteLine("}");
    }
}